package com.company.ljh.medium;
/**
 * 567.给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 *
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 *输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/permutation-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/5/29 22:17
 * @version:1.0
 */
public class 字符串的排列 {
    /**
     * 滑动窗口法，保证窗口内每个字符都是s1中的字符，且每个字符数量小于等于s1
     */
    public boolean checkInclusion(String s1, String s2) {
        //将s1保存为array便于判断;
        int s1Array[] = new int[255];
        for(char c:s1.toCharArray()){
            s1Array[c] +=1;
        }
        int start =0;
        int end = 0;
        int s2Array[] = new int[255];
        int size = 0;
        for(char c:s2.toCharArray()){
            if(s1Array[c] > 0){
                s2Array[c] +=1;
                size++;
                //向左滑动保证改字符数量不超过规定长度
                while(s2Array[c] > s1Array[c]){
                    s2Array[s2.charAt(start++)] -=1;
                    size --;
                }
                if(size == s1.length()){
                    return true;
                }
            }else{
                s2Array = new int[255];
                size =0;
                start = end+1;
            }
            end++;
        }
        return false;
    }
}
